package com.company.lru;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @ClassName LRU
 * @Description TODO
 * @Author 11
 * @Date 2021/3/1 12:44
 * @Version 1.0
 */
public class LRU<V> {
    // 缓存存储上限
    private int limit;
    private final ListNode<String, V> head;
    private final ListNode<String, V> tail;

    private final Map<String, ListNode<String, V>> table = new ConcurrentHashMap<>();//hashmap记录Node
    public LRU(int limit){
        this();
        this.limit=limit;
    }
    public LRU(){//初始化头尾节点
        head = new ListNode<>();
        tail = new ListNode<>();
        head.next = tail;
        head.prev = null;
        tail.prev = head;
        tail.next = null;

    }

    public void get(String key){
        ListNode<String,V> node = table.get(key);
        //如果Node不在表中，代表缓存中并没有
        if (node == null) {
            return;
        }
        //如果存在，则需要移动Node节点到表头  最近使用过 放到表头
        //截断链表，node.prev -> node  -> node.next ====> node.prev -> node.next
        //         node.prev <- node <- node.next  ====>  node.prev <- node.next
        node.prev.next = node.next;
        node.next.prev = node.prev;
        //移动节点到表头
        node.next = head.next;
        head.next.prev = node;
        node.prev = head;
        head.next = node;
        //存在缓存表

        table.put(key, node);

    }

    public void put(String key, V value) {
        ListNode<String, V> node = table.get(key);
        //如果Node不在表中，代表缓存中并没有
        if (node == null) {
            if (table.size() == limit) {
                //超过容量了 ,首先移除尾部的节点
                table.remove(tail.prev.key);//移除尾节点的上一个节点
                tail.prev.prev.next = tail;//尾部的上上个节点的下个节点设置为尾节点
                tail.prev = tail.prev.prev;//尾部的上个节点设置为尾部的上上个节点
            }
            node = new ListNode<>();
            node.key = key;
            node.value = value;
            table.put(key, node);
        }
        //如果存在，则需要移动Node节点到表头
        node.next = head.next;
        head.next.prev = node;
        node.prev = head;
        head.next = node;


    }
    @Override
    public String toString() {
        return "{" +
                "capacity=" + limit +
                ", table=" + table +
                '}'+"\n";
    }



    //静态内部类  首先实现双链表的节点类
    public static class ListNode<K,V>{
        private K key;
        private V value;

        ListNode<K, V> prev;
        ListNode<K, V> next;

        //有参构造函数
        public ListNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
        //无参构造
        public ListNode(){

        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    public static void main(String[] args) {
        LRU<ListNode> cache = new LRU<>(4);
        ListNode<String, Integer> node1 = new ListNode<>("key1", 1);
        ListNode<String, Integer> node2 = new ListNode<>("key2", 2);
        ListNode<String, Integer> node3 = new ListNode<>("key3", 3);
        ListNode<String, Integer> node4 = new ListNode<>("key4", 4);
        ListNode<String, Integer> node5 = new ListNode<>("key5", 5);
        cache.put("key1", node1);
        System.out.println("插入了："+node1);
        System.out.println(cache);
        cache.put("key2", node2);
        System.out.println("插入了："+node2);
        System.out.println(cache);
        cache.put("key3", node3);
        System.out.println("插入了："+node3);
        System.out.println(cache);
        cache.put("key4", node4);
        System.out.println("插入了："+node4);
        System.out.println(cache);
        cache.get("key2");
        System.out.println("获取了："+node2);
        System.out.println(cache);
        cache.put("key5", node5);
        System.out.println("插入了："+node5);
        System.out.println(cache);
        cache.get("key2");
        System.out.println("获取了："+node2);
        System.out.println(cache);
    }

}
